/* File:     hw3_pthread.c
 *
 * Purpose:  Estimate pi using series
 *
 *              pi = 4*[1 - 1/3 + 1/5 - 1/7 + 1/9 - . . . ]
 *
 * Compile:  gcc -g -Wall -o hw3_pthread hw3_pthread.c -lm -lpthread
 *
 *
 * Run:      ./hw3_pthread <number of threads> <n>
 *           n is the number of terms of the Maclaurin series to use
 *           n should be evenly divisible by the number of threads
 *
 * Input:    none
 * Output:   The estimate of pi using multiple threads, one thread, and the
 *           value computed by the math library arctan function
 *           Also elapsed times for the multithreaded and singlethreaded
 *           computations.
 *
 * Notes:
 *    1.  The radius of convergence for the series is only 1.  So the
 *        series converges quite slowly.
 *
 */
 /*????????
?????pthread?е?semaphore????е?????ο??μ?5 page 46????
????е????????ο??μ??е????????ο????????????????????????????
?????????????homework3.zip?????е?????????????????鱨?档

??????
??????????????? ????? ?? ??鱨?? ????zip????????
?????? 4??11??23:59?
????????????????*/

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <pthread.h>
#include <semaphore.h>
#include <sys/time.h>


#define GET_TIME(now) { \
   struct timeval t; \
   gettimeofday(&t, NULL); \
   now = t.tv_sec + t.tv_usec/1000000.0; \
}
//?????н?us????s??????λ
//???????????????????м???pi?????????


const int MAX_THREADS = 1024;//????????

long thread_count;//???????
long long n;//????????
double sum;//????????????????????pi?????????

sem_t sem;//?????

void* Thread_sum(void* rank);

/* Only executed by main thread */
void Get_args(int argc, char* argv[]);
void Usage(char* prog_name);
double Serial_pi(long long n);

int main(int argc, char* argv[]) {
   long       thread;  /* ??64λ???????long */
   pthread_t* thread_handles;
   //pthread_t ???????????ID
   double start, finish, elapsed;

   /* ?????????????????????????????? */
   n = 10000;
   thread_count = 4;

   /* You can also get number of threads from command line */
   //Get_args(argc, argv);

   thread_handles = (pthread_t*) malloc (thread_count*sizeof(pthread_t));//???????????
   sem_init(&sem, 0, 1);//??????????
   sum = 0.0;//?????????????0

   GET_TIME(start);//???????????е??????
   for (thread = 0; thread < thread_count; thread++)
      pthread_create(&thread_handles[thread], NULL,Thread_sum, (void*)thread);//???????
      //?????????????????????????
      //?????????????????????????
      //??????????????????к?????????????
      //???????????????к??????????

   for (thread = 0; thread < thread_count; thread++)
      pthread_join(thread_handles[thread], NULL);
      //????pthread_join???????????????????
      //?????????????????????????????????????????????????????????????洢???????????????
      //????????????????????????????????????????????????????????????
      //???????????????????????????????
      //?????????????????????δ??????????????????λ?????????????????????????????????С?
   GET_TIME(finish);//???????????е???????
   elapsed = finish - start;//???????????????

   sum = 4.0*sum;//1/4*pi*4=pi????????????1/4*pi??
   printf("With n = %lld terms,\n", n);//???????
   printf("   Our estimate of pi = %.15f\n", sum);//?????????pi?
   printf("The elapsed time is %e seconds\n", elapsed);//????????????
   GET_TIME(start);//??????м?????????
   sum = Serial_pi(n);//???м???pi???????????
   GET_TIME(finish);//??????м??????????
   elapsed = finish - start;//?????м???????????
   printf("   Single thread est  = %.15f\n", sum);//???м???????pi?
   printf("The elapsed time is %e seconds\n", elapsed);//???м??????????
   printf("                   pi = %.15f\n", 4.0*atan(1.0));//arctan????pi?

	sem_destroy(&sem);//????????
   free(thread_handles);//??????????
   return 0;
}  /* main */

/*------------------------------------------------------------------*/
void* Thread_sum(void* rank) {
   long my_rank = (long) rank;
   //????????????С???????????????????????????????????????
   //???????????????????????64λ??int????32λ
   //???????棬??????????long???滻int??
   double my_sum = 0.0;//?????????????????????????????sum??
   /*******************************************************************/
   double flag;//????????????????????
   long long i;
   long long group_num=n/thread_count;//???????????????????????????????????????
   long long group_first_i=group_num*my_rank;//???????????п??????????
   long long group_last_i=group_first_i+group_num;//?????????????????????????
   if(group_first_i%2==0){
      flag=1.0;
   }
   else{
      flag=-1.0;
   }
   for(i=group_first_i;i<=group_last_i-1;i++){//???????????????
      my_sum+=flag/(2*i+1);//1/4pi??????
      flag*=-1;//?????????????
   }
   sem_wait(&sem);//???????????????????
   sum+=my_sum;//????????????????????????????????sum
   sem_post(&sem);//????????
   /******************************************************************/
   return NULL;
}  /* Thread_sum */

/*------------------------------------------------------------------
 * Function:   Serial_pi
 * Purpose:    Estimate pi using 1 thread
 * In arg:     n
 * Return val: Estimate of pi using n terms of Maclaurin series
 */
double Serial_pi(long long n) {
   double sum = 0.0;
   long long i;
   double factor = 1.0;

   for (i = 0; i < n; i++, factor = -factor) {
      sum += factor/(2*i+1);//????????????????
   }
   return 4.0*sum;//??4?????pi?

}  /* Serial_pi */

/*------------------------------------------------------------------
 * Function:    Get_args
 * Purpose:     Get the command line args
 * In args:     argc, argv
 * Globals out: thread_count, n
 */
void Get_args(int argc, char* argv[]) {
   if (argc != 3) Usage(argv[0]);
   thread_count = strtol(argv[1], NULL, 10);
   if (thread_count <= 0 || thread_count > MAX_THREADS) Usage(argv[0]);
   n = strtoll(argv[2], NULL, 10);
   if (n <= 0) Usage(argv[0]);
}  /* Get_args */


/*------------------------------------------------------------------
 * Function:  Usage
 * Purpose:   Print a message explaining how to run the program
 * In arg:    prog_name
 */
void Usage(char* prog_name) {
   fprintf(stderr, "usage: %s <number of threads> <n>\n", prog_name);
   fprintf(stderr, "   n is the number of terms and should be >= 1\n");
   fprintf(stderr, "   n should be evenly divisible by the number of threads\n");
   exit(0);
}  /* Usage */
